package algorithm.sort.quick;


import algorithm.sort.base.ArrayUtils;

public class QuickSort {
    public static void sort(int[] data) {
        sortPart(data, 0, data.length - 1);
    }

    public static void sortPart(int[] data, int start, int end) {
        if (end > start) {
            int mid = partition(data, start, end);
            sortPart(data, start, mid - 1);
            sortPart(data, mid + 1, end);
        }
    }

    public static int partition(int[] data, int leftIndex, int rightIndex) {
        int partitionData = data[leftIndex];
        int startIndex = leftIndex;
        while (leftIndex < rightIndex) {
            while (leftIndex < rightIndex && data[rightIndex] > partitionData) {
                rightIndex--;
            }
            while (leftIndex < rightIndex && data[leftIndex] <= partitionData) {
                leftIndex++;
            }
            if (leftIndex < rightIndex) {
                ArrayUtils.swap(data, leftIndex, rightIndex);
            }
        }
        ArrayUtils.swap(data, leftIndex, startIndex);
        return leftIndex;
    }
}
